/**
 * Created With IntelliJ IDEA
 * Description:牛客网:NC297 删除一个二叉搜索树中的节点
 * <a href="https://www.nowcoder.com/practice/c1c2970c7a3e442b8e41423e88d099fb?tpId=196&tqId=39788&ru=/exam/oj">...</a>
 * User: DELL
 * Data: 2023-03-05
 * Time: 15:41
 */


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
     public TreeNode(int val)
     {
         this.val = val;
    }
}


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param key int整型
     * @return TreeNode类
     */
    public TreeNode deleteNode (TreeNode root, int key) {
        TreeNode parent = null;
        TreeNode cur = root;
        //寻找值为key的结点和其父节点
        while (cur != null) {
            if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                break;
            }
        }
        //不存在值为key的结点
        if (cur == null) {
            return root;
        }
        //分类讨论,删除结点
        if (cur.left == null) {  //左结点为空时
            if (cur == root) {
                //cur是根节点时
                root = root.right;
            } else  if (parent.left == cur){
                //cur是其父节点的左孩子结点时
                parent.left = cur.right;
            } else {
                //cur是其父节点的右孩子结点时
                parent.right = cur.right;
            }
        } else if (cur.right == null) {  //右结点为空时
            if (cur == root) {
                //cur是根节点时
                root = root.left;
            } else  if (parent.left == cur){
                //cur是其父节点的左孩子结点时
                parent.left = cur.left;
            } else {
                //cur是其父结点的右孩子结点时
                parent.right = cur.left;
            }
        } else {  //左右结点均不为空时 --- 替换法 (这里找的是左子树的值最大的结点替换)
            //1.寻找替换的结点,并且将该结点从原二叉树中删除出来
            TreeNode parent2 = cur;
            TreeNode cur2 = cur.left;
            if (cur2.right == null) {
                parent2.left = cur2.left;
            } else {
                while (cur2.right != null) {
                    parent2 = cur2;
                    cur2 = cur2.right;
                }
                parent2.right = cur2.left;
            }
            //3.替换原结点
            if (cur != root) {  //不是根节点
                if (cur == parent.left) {  //cur是其父结点的左孩子结点
                    parent.left = cur2;
                } else {  //cur是其父结点的右孩子结点
                    parent.right = cur2;
                }
            } else {
                root = cur2;
            }
            cur2.left = cur.left;
            cur2.right = cur.right;
        }
        return root;
    }
}